Năm 1504, Christopher Columbus bị mắc cạn ở Jamaica nên gởi một số thủy thủ xuống xuồng nhỏ đến Hispaniola cầu cứu. Họ đâm vào đảo trên đường đi nhưng nó không có nước. Họ gọi nó là Navaza (nava- có nghĩa là "bằng phẳng"), và từ đó các nhà đi biển thường hay né tránh nó trong 350 năm tiếp theo.

Năm 1857 Peter Duncan, một thuyền trưởng của Mỹ tuyên bố chủ quyền trên Đảo Navassa. Đây là đảo thứ ba được tuyên bố chủ quyền theo Đạo luật Đảo Phân chim năm 1856 vì đảo có nhiều tích trử phân chim. Phân chim được khai thác từ năm 1865 đến 1898. Haiti chống đối sự thôn tính đảo này nhưng Hoa Kỳ bác bỏ tuyên bố chủ quyền của Haiti và từ tháng 10 năm 1857 tuyên bố đảo này là một lãnh thổ chưa sáp nhập của Hoa Kỳ.

Phosphate trong phân chim là một loại phân bón hữu cơ siêu đẳng đã trở thành nguồn phân chính dùng trong nông nghiệp Mỹ suốt giữa thế kỷ 19. Duncan chuyển quyền người tìm ra đảo cho ông chủ của ông, một nhà buôn phân chim người Mỹ ở Jamaica. Nhà buôn này sau đó bán nó lại cho công ty vừa mới thành lập là Công ty Phosphate Navassa tại Baltimore, Maryland. Sau khi gián đoạn vì Nội chiến Hoa Kỳ, công ty này xây các cơ sở khai thác phân chim lớn hơn trên Navassa cùng với các gia cư đơn giản cho 140 lao động hợp đồng người da đen từ Maryland, nhà dành riêng cho các giám thị da trắng, một tiệm đồ sắt, kho chứa và một nhà thờ. Khai thác phân bắt đầu từ năm 1865. Công nhân đào phân bằng thuốc nổ và búa rồi bỏ vào các xe có đường rai đưa ra điểm vận chuyển ở Vịnh Lulu. Từ chỗ này phân được vào bao và hạ xuống tàu nhỏ vận chuyển ra xà lan của công ty.

Đảo Navassa

Khuân vác phân chim bằng sức người trong điều kiện khắc nghiệt của nắng nóng nhiệt đới cộng với sự bực tức thông thường vì điều kiện sống trên đảo dần gây ra một cuộc nổi loạn trên đảo vào năm 1889. Năm giám thị bị giết chết trong cuộc ẩu đả. Một chiến hạm của Hoa Kỳ đưa 18 trong số các công nhân về Baltimore cho ba cuộc xử án riêng lẻ về cáo buột sát nhân. Một hội kín người da đen có tên là Order of Galilean Fisherman gây quỹ để biện hộ cho các công nhân khai thác trước tòa án liên bang, và phần biện hộ dựa vào luận điểm rằng các bị cáo hành động vì tự vệ hoặc trong lúc nóng giận và trong mọi trường hợp Hoa Kỳ không có quyền pháp lý riêng tại đảo. Các vụ xử bao gồm Jones versus Hoa Kỳ[1] được đưa lên đến Tối cao Pháp viện Hoa Kỳ tháng 10 năm 1890. Tại đây tòa xử Đạo luật Đảo Phân chim là hợp hiến và ba trong số các thợ mỏ chờ ngày hành quyết trong mùa xuân năm 1891. Một cuộc vận động với thỉnh nguyện thơ do các nhà thờ người da đen trên toàn quốc tổ chức cũng được ký bởi các bồi thẩm viên da trắng từ ba vụ xử đã tới tay Tổng thống Benjamin Harrison. Tuy nhiên ông chỉ giảm án đến giam giữ.

Khai thác phân chim tiếp tục trở lại trên Navassa nhưng ở mức độ ít hơn trước nhiều. Chiến tranh Tây Ban Nha-Hoa Kỳ năm 1898 bắt buộc Công ty Phosphate di tản đảo và khai phá sản. Các chủ mới bỏ đảo cho chim biển tự do sinh sống sau năm 1901.

Hải đăng Đảo Navassa. Khu cư ngụ của nhân viên giữ hải đăng ở hậu cảnh.Dấu vết còn lại của khu cư ngụ cho các người giữ Hải đăng Navassa

Navassa trở nên nổi bật trở lại với việc mở cửa Kênh đào Panama năm 1914. Đường hàng hải giữa duyên hải phía đông của Hoa Kỳ và kinh đào đi ngang qua Hành lang Windward giữa Cuba và Haiti. Navassa từ trước đến giờ là nơi nguy hiểm cho lưu thông hàng hải nên cần một hải đăng. Cục Hải đăng Hoa Kỳ xây Hải đăng Navassa có tháp cao 162 bộ (46 mét) và 395 bộ (120 mét) trên mặt biển vào năm 1917. Một trưởng trạm và hai phụ tá được nhận lệnh sống ở đây cho đến khi Cục Hải đăng Hoa Kỳ cài đặt một đèn hiệu tự động vào năm 1929. Sau khi sáp nhập dịch vụ hải đăng năm 1939, Lực lượng Tuần Duyên Hoa Kỳ sửa chữa hải đăng hai lần mỗi năm. Hải quân Hoa Kỳ dựng một đài quan sát trong suốt Chiến tranh thế giới thứ hai. Đảo không có người ở kể từ đó.

Một đoàn thám hiểm khoa học của Đại học Harvard đã nghiên cứu đất và đời sống biển của đảo năm 1930. Kể từ Chiến tranh thế giới thứ hai, các đài phát thanh không chuyên nghiệp đã thường xuyên lên đảo để phát thanh từ lãnh thổ này. Dân đánh cá chính yếu là từ Haiti đến để đánh bắt cá quanh vùng nước của đảo.

Từ 1903 đến 1917, Navassa là một phần phụ thuộc của Căn cứ Hải quân Vịnh Guantanamo, và từ 1917 đến 1996 nó được quản lý bởi Tuần Duyên Hoa Kỳ. Từ ngày 16 tháng 1 năm 1996 do Bộ Nội vụ Hoa Kỳ quản lý.

Ảnh chụp từ trên không cho thấy duyên hải có bờ đá dốc vây quanh đảo

Ngày 29 tháng 8 năm 1996, Tuần Duyên Hoa Kỳ tháo gở hải đăng trên Navassa. Một lực lượng đặc biệt liên hợp lãnh đạo bởi Bộ Ngoại giao Hoa Kỳ chuyển đảo cho Bộ Nội vụ Hoa Kỳ. Bằng Sắc lệnh Bộ trưởng số 3205[2] ngày 16 tháng 1 năm 1997, Bộ Nội vụ nhận lại việc kiểm soát đảo và đặt đảo dưới quyền Phòng Quốc hải vụ Hoa Kỳ. Vì mục đích thống kê, Navassa trước đây được xếp vào nhóm đảo mà thuật từ nay không còn dùng nữa đó là "Các Đảo Caribbean Linh tinh của Hoa Kỳ" (United States Miscellaneous Caribbean Islands) và hiện tại được xếp nhóm với các đảo khác đã tuyên bố chủ quyền theo Đạo luật Đảo Phân chim gọi là Các tiểu đảo xa của Hoa Kỳ.

Một cuộc thám hiểm khoa học năm 1998 dẫn đầu bởi Trung tâm Bảo tồn Biển ở Washington D.C. diễn tả Navassa như "một khu vực đa dạng sinh học cá biệt của biển Caribbean". Đất đai và hệ sinh thái ngoài khơi của đảo vẫn tồn tại qua thế kỷ 20 hầu như không bị đụng đến.

Bằng Sắc lệnh Bộ trưởng số 3210[3] ngày 3 tháng 12 năm 1999, Cục Bảo vệ Cá và Hoang dã Hoa Kỳ nhận lại trách nhiệm quản lý Navassa và nó trở thành Vùng Bảo vệ Hoang dã Quốc gia Hoa Kỳ. Phòng Quốc hải vụ giữ thẩm quyền về chính trị vụ của đảo và quyền pháp lý được thực hiện trực tiếp bởi tòa án sơ thẩm Hoa Kỳ gần nhứt. Lối vào đảo Navassa rất nguy hiểm và du khách cần có giấy phép từ Cục Bảo vệ Cá và Hoang dã Hoa Kỳ ở Boqueron, Puerto Rico để vào vùng nước của lãnh thổ. Từ khi thay đổi tình trạng chính sách, các đài phát thanh không chuyên bị từ chối cho vào đảo.